#include <deque>
#include <vector>
#include <string>
#include <cstring>
#include <fstream>
#include <iostream>
#include <algorithm>

#include "syn.hpp"

using namespace std;

// 求各符号出现在其右侧的产生式
void Syn::get_appears() {
	for (auto iter = symbols.begin(); iter != symbols.end(); ++iter) {
		appears[*iter] = vector<int>();
		for (int i = 0; i < produce.size(); ++i) {
			for (int j = 0; j < produce[i].second.size(); ++j) {
				if (produce[i].second[j] == *iter) {
					appears[*iter].push_back(i);
					break;
				}
			}
		}
	}
}

// 打印各符号出现的产生式
void Syn::print_appears() {
	cout << "Appears:" << endl;
	for (auto iter = symbols.begin(); iter != symbols.end(); ++iter) {
		auto appear = appears[*iter];
		cout << *iter << ": ";
		for (int cnt = 0; cnt < appear.size(); ++cnt) {
			cout << appear[cnt] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

// 求取决定/依赖关系，即一个符号的Follow集是否与其规约的非终结符的Follow集有关
void Syn::get_determine() {
	for (auto iter = symbols.begin(); iter != symbols.end(); ++iter) {
		determine[*iter] = (vector<string>());
		for (int cnt = 0; cnt < produce.size(); ++cnt) {
			if (produce[cnt].first == *iter) {
				vector<string> &items = produce[cnt].second;
				for (int i = 0; i < items.size(); ++i) {
					int j;
					for (j = i+1; j < items.size(); ++j) {
						if (!empty_map[items[j]]) {
							break;
						}
					}
					if (j == items.size()) {
						if (*iter != items[i]) {
							determine[*iter].push_back(items[i]);
						}
					}
				}
			}
		}
	}
}

// 打印决定/依赖关系
void Syn::print_determine() {
	cout << "Determine:" << endl;
	for (auto iter = symbols.begin(); iter != symbols.end(); ++iter) {
		cout << *iter << " => ";
		vector<string> &items = determine[*iter];
		for (auto item = items.begin(); item != items.end(); ++item) {
			cout << *item << " ";
		}
		cout << endl;
	}
	cout << endl;
}

// 求取当前状态下sym的Follow集
unordered_set<string> Syn::get_follow(string &sym) {
	unordered_set<string> res;
	auto appear = appears[sym];
	for (auto iter = appear.begin(); iter != appear.end(); ++iter) {
		int i;
		auto rule = produce[*iter].second;
		for (i = 0; i < rule.size(); ++i) {
			if (rule[i] == sym) {
				break;
			}
		}
		++i;
		for (; i < rule.size(); ++i) {
			auto this_first = first_set[rule[i]];
			res.insert(this_first.begin(), this_first.end());
			if (!empty_map[rule[i]]) {
				break;
			}
		}
		if (i == rule.size()) {
			if (follow_set.find(produce[*iter].first) != follow_set.end()) {
				auto this_follow = follow_set[produce[*iter].first];
				res.insert(this_follow.begin(), this_follow.end());
			}
		}
	}
	
	if (res.find("$") != res.end()) { // 删除空字符
		res.erase(res.find("$"));
	}

	return res;
}

void Syn::infer_follow_set() {
	// 推导Follow集需要首先推导First集、符号出现位置以及决定/依赖关系
	if (first_set.empty()) {
		this->infer_first_set();
	}
	if (appears.empty()) {
		this->get_appears();
	}
	if (determine.empty()) {
		this->get_determine();
	}

	deque<string> que;

	// 初次遍历，获取最初的follow集
	follow_set[start] = this->get_follow(start);
	follow_set[start].insert("$");
	que.push_back(start);
	for (int cnt = 0; cnt < symbols.size(); ++cnt) {
		if (symbols[cnt] == start) {
			continue;
		}
		follow_set[symbols[cnt]] = this->get_follow(symbols[cnt]);
		que.push_back(symbols[cnt]);
	}

	while(!que.empty()) {
		string sym = que.front();
		que.pop_front();
		auto new_follow = this->get_follow(sym);
		if (follow_set[sym].size() < new_follow.size()) { // sym的follow集存在更新
			auto items = determine[sym];
			for (auto iter = items.begin(); iter != items.end(); ++iter) {
				que.push_back(*iter); // 将所有依赖于sym的符号加入到队列中
			}
			follow_set[sym] = new_follow;
		}
	}
}

void Syn::print_follow_set() {
	cout << "Follow Sets:" << endl;
	for (auto iter = symbols.begin(); iter != symbols.end(); ++iter) {
		cout << *iter << " => ";
		auto follow_syms = follow_set[*iter];
		for (auto i = follow_syms.begin(); i != follow_syms.end(); ++i) {
			cout << *i << " ";
		}
		cout << endl;
	}
	cout << endl;
}
